1. Technical Field
The invention relates generally to digital integrated circuits and, more particularly, to digital adders using carry lookahead. More particularly still, the present invention relates to carry lookahead adders having minimum gate levels and gates with limited fanin and fanout.
2. Description of the Related Art
The typical digital microprocessor uses a digital, or binary, adder. The adder is typically used to provide numerical sums as well as to implement numerous other logic functions. In a typical microprocessor, many adders are used for these functions. When two digital words are added, the carry bit that results from the addition of the lesser significant bits must be considered. This can easily be done by rippling a carry signal as the addition is performed. A problem with this, particularly for large words, is that substantial time is required to ripple the carry signals through the entire addition chain. Further, since the adders are often performing adder functions in critical time paths, the time needed to ripple the carry signal can slow up the microprocessor. Therefore, various adder designs employing carry lookahead or carry skip logic have been used.
One such method for implementing an adder is described in the article by R. K. Montoye, "Area-time efficient addition in charge based technology," 19th Design Automation Conference, pp. 862-872, June 1981. In Montoye, the number of stages of logic needed to compute all carries is log n (base 2). Thus, the carries of a 16-bit adder can be developed in four stages, the carries for a 32-bit adder can be developed in five stages and for a 64-bit adder, they can be developed in six stages. Unfortunately, the worst fanout at each stage doubles and reaches n/2 for one of the inputs to the last stage.
Another well-known method is described in R. P. Brent and H. T. Kung, "A regular layout for parallel adders," IEEE Trans. on Computers, vol. C-31, pp. 260-264, March 1982. In the Brent and Kung teaching, the method limits the fanout to two but with a gate delay of 2(log n)-1 stages.
The basic circuit used in both of the above designs is one that merges the "group carry generate" and "group carry propagate" signals from a pair of similar circuits in the previous stage, to produce a new pair of generate and propagate signals. Yet, both methods still suffer from delay problems, one due to large fanout on some gates, the other due to nearly doubling the number of gate levels.
Accordingly, what is needed is an improved design for carry lookahead adders that has a minimum number of gate levels and also limits the maximum fanout, thus resulting in faster operation.